#include <iostream>
#include <string>
#include "DecTree.h"

using namespace std;

void DecTree::process()
{
	while( true )
	{
		string command;
		cin >> command;
		if( command == "add" )
		{
			int data;
			cin >> data;
			add( data );
		}
		if( command == "insert" )
		{
			int n, data;
			cin >> n;
			cin >> data;
			insert( n, data );
		}
		if( command == "sum" )
		{
			int from, to;
			cin >> from;
			cin >> to;
			cout << sum( from, to ) << endl;
		}
		if( command == "delete" )
		{
			int n;
			cin >> n;
			del( n );
		}
		if( command != "add" && command != "insert" && command != "sum" && command != "delete" )
		{
			cout << "Incorrect input\n";
		}
	}
};

void DecTree::insert( int n, int data )
{
	Node* newNode = new Node( data );
	newNode->size = 1;
	if( root == 0 )
	{
		if( n != 0 )
		{
			cout << "Out of range\n";
			return;
		}
		root = newNode;
		return;
	}
	if( n == 0 )
	{
		root = merge( newNode, root );
		return;
	}
	else
	{
		if( n == root->size )
		{
			root = merge( root, newNode );
			return;
		}
		else
		{
			if( n < 0 || n > root->size )
			{
				cout << "Out of range\n";
				return;
			}
			Node *leftN, *rightN;
			split( root, n, leftN, rightN );
			leftN = merge( leftN, newNode );
			root = merge( leftN, rightN );
		}
	}
};

void DecTree::add( int data )
{
	if( root != 0 )
	{
		insert( size(), data );
	}
	else
	{
		insert( 0, data );
	}
};

void DecTree::del( int n )
{
	if( n < 0 || n > size() )
	{
		cout << "Incorrect input\n";
		return;
	}
	Node *left = 0, *middle = 0, *right = 0;
	int _size = 0;
	split( root, n, left, right );
	if( left != 0 )
	{
		_size = left->size;
	}
	split( right, n - _size + 1, middle, right );
	root = merge( left, right );
	return;
};

int DecTree::sum( int from, int to )
{
	if( root == 0 || from < 0 || from > to || to > root->size )
	{
		cout << "Incorrect input\n";
		exit(1);
	}
	Node *leftN, *rightN, *middle;
	split( root, from, leftN, middle );
	split( middle, to - from, middle, rightN );
	int result = middle->data;
	middle = merge( middle, rightN );
	root = merge( leftN, middle );
	return result;
};

int DecTree::size()
{
	if( root == 0 ) 
	{
		return 0;
	}
	else
	{
		return root->size;
	}
};

void DecTree::split( Node* to_split, int n, Node*& left, Node*& right )
{
	if( to_split == 0 )
	{
		left = 0;
		right = 0;
		return;
	}
	if( n == 0 )
	{
		left = 0;
		right = to_split;
		return;
	}
	if( n == to_split->size )
	{
		left = to_split;
		right = 0;
		return;
	}
	if( to_split->left == 0 || to_split->left->size < n )
	{
		left = to_split;
		Node *newNode = 0;
		if( to_split->right != 0 )
		{
			left->data -= left->right->data;
			left->size -= left->right->size;
		}
		if( to_split->left == 0 )
		{
			n -= 1;
		}
		else
		{
			n = n - to_split->left->size - 1;
		}

		split( to_split->right, n, newNode, right );
		left->right = newNode;
		
		if( newNode != 0 )
		{
			left->size += newNode->size;
			left->data += newNode->data;
		}
	}
	else
	{
		right = to_split;
		Node* newNode;
		if( to_split->left != 0 )
		{
			right->data -= to_split->left->data;
			right->size -= to_split->left->size;
		}

		split( to_split->left, n, left, newNode );
		right->left = newNode;

		if( newNode != 0 )
		{
			right->data += newNode->data;
			right->size += newNode->size;
		}
	}
	return;
};

Node* DecTree::merge( Node* left, Node* right )
{
	if( left == 0 )
	{
		return right;

	}
	if( right == 0 )
	{
		return left;
	}
	if( left->priority > right->priority )
	{
		if( left->right != 0 )
		{
			left->size -= left->right->size;
			left->data -= left->right->data;
		}
		left->right = merge( left->right, right );

		left->size += left->right->size;
		left->data += left->right->data;
		return left;
	}
	else
	{
		if( right->left != 0 )
		{
			right->size -= right->left->size;
			right->data -= right->left->data;
		}
		right->left = merge( left, right->left );

		right->size += right->left->size;
		right->data += right->left->data;
		return right;
	}
};